package org.apache.lucene.index;

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.io.IOException;

import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.store.RAMOutputStream;

/**
 * This abstract class writes skip lists with multiple levels.
 * 
 * Example for skipInterval = 3: c (skip level 2) c c c (skip level 1) x x x x x
 * x x x x x (skip level 0) d d d d d d d d d d d d d d d d d d d d d d d d d d
 * d d d d d d (posting list) 3 6 9 12 15 18 21 24 27 30 (df)
 * 
 * d - document x - skip data c - skip data with child pointer
 * 
 * Skip level i contains every skipInterval-th entry from skip level i-1.
 * Therefore the number of entries on level i is: floor(df / ((skipInterval ^ (i +
 * 1))).
 * 
 * Each skip entry on a level i>0 contains a pointer to the corresponding skip
 * entry in list i-1. This guarantess a logarithmic amount of skips to find the
 * target document.
 * 
 * While this class takes care of writing the different skip levels, subclasses
 * must define the actual format of the skip data.
 * 
 */
abstract class MultiLevelSkipListWriter {
	// number of levels in this skip list
	private int numberOfSkipLevels;

	// the skip interval in the list with level = 0
	private int skipInterval;

	// for every skip level a different buffer is used
	private RAMOutputStream[] skipBuffer;

	protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels,
			int df) {
		this.skipInterval = skipInterval;

		// calculate the maximum number of skip levels for this document
		// frequency
		numberOfSkipLevels = df == 0 ? 0 : (int) Math.floor(Math.log(df)
				/ Math.log(skipInterval));

		// make sure it does not exceed maxSkipLevels
		if (numberOfSkipLevels > maxSkipLevels) {
			numberOfSkipLevels = maxSkipLevels;
		}
	}

	protected void init() {
		skipBuffer = new RAMOutputStream[numberOfSkipLevels];
		for (int i = 0; i < numberOfSkipLevels; i++) {
			skipBuffer[i] = new RAMOutputStream();
		}
	}

	protected void resetSkip() {
		// creates new buffers or empties the existing ones
		if (skipBuffer == null) {
			init();
		} else {
			for (int i = 0; i < skipBuffer.length; i++) {
				skipBuffer[i].reset();
			}
		}
	}

	/**
	 * Subclasses must implement the actual skip data encoding in this method.
	 * 
	 * @param level
	 *            the level skip data shall be writting for
	 * @param skipBuffer
	 *            the skip buffer to write to
	 */
	protected abstract void writeSkipData(int level, IndexOutput skipBuffer)
			throws IOException;

	/**
	 * Writes the current skip data to the buffers. The current document
	 * frequency determines the max level is skip data is to be written to.
	 * 
	 * @param df
	 *            the current document frequency
	 * @throws IOException
	 */
	void bufferSkip(int df) throws IOException {
		int numLevels;

		// determine max level
		for (numLevels = 0; (df % skipInterval) == 0
				&& numLevels < numberOfSkipLevels; df /= skipInterval) {
			numLevels++;
		}

		long childPointer = 0;

		for (int level = 0; level < numLevels; level++) {
			writeSkipData(level, skipBuffer[level]);

			long newChildPointer = skipBuffer[level].getFilePointer();

			if (level != 0) {
				// store child pointers for all levels except the lowest
				skipBuffer[level].writeVLong(childPointer);
			}

			// remember the childPointer for the next level
			childPointer = newChildPointer;
		}
	}

	/**
	 * Writes the buffered skip lists to the given output.
	 * 
	 * @param output
	 *            the IndexOutput the skip lists shall be written to
	 * @return the pointer the skip list starts
	 */
	long writeSkip(IndexOutput output) throws IOException {
		long skipPointer = output.getFilePointer();
		if (skipBuffer == null || skipBuffer.length == 0)
			return skipPointer;

		for (int level = numberOfSkipLevels - 1; level > 0; level--) {
			long length = skipBuffer[level].getFilePointer();
			if (length > 0) {
				output.writeVLong(length);
				skipBuffer[level].writeTo(output);
			}
		}
		skipBuffer[0].writeTo(output);

		return skipPointer;
	}

}
